from typing import Tuple

# 求最长递增子序列 (Longest Increasing Subsequence, LIS)
def LIS(a: list[int]) -> Tuple[int, list[int]]:
    # dp[i] 储存以a[i]为结尾的最长递增子序列的长度
    # 对于每个数字，其本身就是长度为1的递增子序列，因此初始化为1
    n = len(a)
    dp = [1] * n

    # last[i] 储存以a[i]为结尾的最长递增子序列中，对应上一个数字的下标位置
    # 根据最优性原理，上一个数字也位于以该数字结尾的最长递增子序列中
    # 因此，我们依次往前查找，就能构建出整个最长递增子序列
    last = [-1] * n

    # 动态规划：我们从第二个数字开始依次完成填表
    for i in range(1, n):
        # 对于len[i]，遍历i前面的结果，尝试找到最大的len[j] + 1 = len[i]
        for j in range(0, i):
            # 首先判断是否满足递增的要求
            if a[j] < a[i]:
                # 然后判断是否找到更大的结果
                if dp[j] + 1 > dp[i]:
                    # 找到更优的结果并更新状态
                    dp[i] = dp[j] + 1
                    last[i] = j

    # 填表完毕，确定最优解的位置
    max_i = max(range(n), key=lambda i: dp[i])

    # 留意last数组是从后往前存储的，我们使用栈进行顺序调整
    seq, i = [], max_i
    while i >= 0:
        seq.append(i)
        i = last[i]
    # 栈翻转后即为最长递增子序列的下标序列
    seq[:] = seq[::-1]

    # 返回答案，包括长度及方案
    return dp[max_i], seq
    
# main
a = [11, 8, 3, 6, 4, 7, 99, 14]
len, seq = LIS(a)
print('最长递增子序列是:', [a[i] for i in seq])
print(f'最长递增子序列的长度为: {len}')
